﻿//归并排序算法(递归思想)
//#include <stdio.h>
//#include <stdlib.h>
//#include <string.h>
//void MergeFunction(int* a, int* nums, int n, int begin, int end) {
//	if (begin == end) {
//		return;
//	}
//	int middle = (begin + end) / 2;
//	MergeFunction(a, nums, n, begin, middle);
//	MergeFunction(a, nums, n, middle + 1, end);
//	int leftbegin = begin, leftend = middle;
//	int rightbegin = middle + 1, rightend = end;
//	int insert = begin;
//	while (leftbegin <= leftend && rightbegin <= rightend) {
//		if (a[leftbegin] < a[rightbegin]) {
//			nums[insert++] = a[leftbegin++];
//		}
//		else {
//			nums[insert++] = a[rightbegin++];
//		}
//	}
//	while (leftbegin <= leftend) {
//		nums[insert++] = a[leftbegin++];
//	}
//	while (rightbegin <= rightend) {
//		nums[insert++] = a[rightbegin++];
//	}
//	memcpy(a + begin, nums + begin, sizeof(int) * (end - begin + 1));
//}
//void MergeSort(int* a, int n) {
//	int* nums = (int*)malloc(sizeof(int) * n);
//	if (!nums) {
//		perror("nums malloc");
//		exit(-1);
//	}
//	MergeFunction(a, nums, n, 0, n - 1);
//	free(nums);
//}
//int main() {
//	int a[] = { 10,6,7,1,3,9,4,2 };
//	MergeSort(a, sizeof(a) / sizeof(int));
//	for (int i = 0; i < sizeof(a) / sizeof(int); i++) {
//		fprintf(stdout, "%d ", a[i]);
//	}
//	puts("");
//	return 0;
//}

//void QuickSort(int* a, int begin, int end)
//{
//	//即当不存在区间时结束，即就排好了一个数
//	if (begin >= end)
//		return;
//	//PartSort1算法是返回一个顺序表中中间值的坐标，在坐标左边都小于此数，在坐标的右边都大于此数
//	int keyi = PartSort2(a, begin, end);
//	// 区间递归: 左[begin, keyi-1] keyi 右[keyi+1, end],一直缩小，最终会逐渐会缩小成排序
//	QuickSort(a, begin, keyi - 1);//在keyi的左面进行遍历
//	QuickSort(a, keyi + 1, end);//在keyi的右面进行遍历
//}//对比之下有些类同